from os import path
from collections import Counter
from functools import lru_cache

with open(path.join(path.dirname(__file__), 'input.txt')) as file:
    lines = file.read().splitlines()
    poly = lines[0]
    rules = {}
    for rule in lines[2:]:
        (key, value) = rule.split(" -> ")
        rules[key] = value

    @lru_cache(maxsize=None)
    def get_counter(poly: str, n: int) -> Counter:
        if n == 0:
            return Counter(poly)
        
        # dive into two pices
        if len(poly) > 2:
            counter = Counter()
            for i in range(len(poly) - 1):
                counter += get_counter(poly[i : i + 2], n)
            return counter - Counter(poly[1:-1]) # each char in poly[1:-1] had been cout twice

        insert_element = rules[poly]
        # AB => ACB 
        # AC + CB
        return get_counter(poly[0] + insert_element, n - 1)\
            + get_counter(insert_element + poly[1], n - 1)\
            - Counter(insert_element) # count twice 'insert_element', so sub once

    counter = get_counter(poly, 40)
    most_common = counter.most_common()
    print(most_common[0][1] - most_common[-1][1])